package argo.hot100.search2mid;

public class FindMedianSortedArrays {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        if (nums2.length < nums1.length) {
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }

        int left = 0, right = nums1.length;
        int totalLeft = (nums1.length + nums2.length + 1) / 2;
        //最终结果需要分界线下标mid1(i)、mid2(j) 满足 nums1[i-1]<=num2[j+1] && nums2[j-1]<=num2[i+1]，若不满足即需要进行二分移动操作
        while (left < right) {
            //在数组长度为奇数的情况让左边更长一个元素，从而避免奇偶长度的讨论
            int mid1 = (left + right + 1) / 2;
            int mid2 = totalLeft - mid1;
            if (nums1[mid1 - 1] > nums2[mid2]) {
                //此时说明目标分割位在左侧，即需要查找较小值才能满足条件
                right = mid1 - 1;
            } else {
                left = mid1;
            }
        }
        int mid1 = left;
        int mid2 = totalLeft - left;
        int nums1LeftMax = mid1 == 0 ? Integer.MIN_VALUE : nums1[mid1 - 1];
        int nums1RightMin = mid1 == nums1.length ? Integer.MAX_VALUE : nums1[mid1];
        int nums2LeftMax = mid2 == 0 ? Integer.MIN_VALUE : nums2[mid2 - 1];
        int nums2RightMin = mid2 == nums2.length ? Integer.MAX_VALUE : nums2[mid2];

        if ((nums1.length + nums2.length) % 2 == 0) {
            return (double) (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2;
        } else {
            return (double) Math.max(nums2LeftMax, nums1LeftMax);
        }

    }

}
